package PrefixSum;

import java.util.HashMap;

//https://leetcode.cn/problems/subarray-sum-equals-k/description/
public class l_560 {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length, sum = 0, ans = 0;
        HashMap<Integer, Integer> hash = new HashMap<>();
        hash.put(0, 1); //防止sum为k
        //前缀和这里优化了, 用sum存dp[i]了
        //枚举子数组的右端点, 通过哈希表统计左边有几个子数组(这里是左端点为0的子数组)的和等于sum - k
        for(int i = 0; i < n; i++)
        {
            sum += nums[i]; //sum代表数组前i + 1个数的和
            ans += hash.getOrDefault(sum - k, 0); //不止一个和为sum - k的子数组(这里是左端点为0的子数组)
            hash.put(sum, hash.getOrDefault(sum, 0) + 1); //把当前sum放入哈希表
        }
        return ans;
    }
}
